﻿#include <iostream>

static int getValue(const int* matrix, const size_t colSize, int x, int y)
{
	return matrix[x + y * colSize];
}

#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)

static void printMatrix(const int* matrix, const size_t rowSize, const size_t colSize)
{
	printf("matrix:\n");
	for (int y = 0; y < rowSize; y++)
	{
		for (int x = 0; x < colSize; x++)
		{
			printf("%d,", matrix[x+y*colSize]);
		}

		printf("\n");
	}
}

static int preprocessing(const int* matrix, const size_t rowSize, const size_t colSize)
{
	int* howManyContinuousOneOnRight = (int*)malloc(rowSize * colSize * sizeof(int));
	memset(howManyContinuousOneOnRight, 0, rowSize * colSize * sizeof(int));
	for (int y = 0; y < rowSize; y++)
	{
		for (int x = 0; x < colSize; x++)
		{
			if (getValue(matrix, colSize, x, y) == 0) continue;

			for (int x1 = x; x1 < colSize; x1++)
			{
				if (getValue(matrix, colSize, x1, y) == 1)
				{
					howManyContinuousOneOnRight[x + y * colSize]++;
				}
				else
				{
					break;
				}
			}
		}
	}

	int* howManyContinuousOneOnDown = (int*)malloc(rowSize * colSize * sizeof(int));
	memset(howManyContinuousOneOnDown, 0, rowSize * colSize * sizeof(int));
	for (int x = 0; x < colSize; x++)
	{
		for (int y = 0; y < rowSize; y++)
		{
			if (getValue(matrix, colSize, x, y) == 0) continue;

			for (int y1 = y; y1 < rowSize; y1++)
			{
				if (getValue(matrix, colSize, x, y1) == 1)
				{
					howManyContinuousOneOnDown[x + y * colSize]++;
				}
				else
				{
					break;
				}
			}
		}
	}

	int minContinuousOne;
	int maxEdgeLen = 0;
	int x1;
	int y1;
	for (int y = 0; y < rowSize; y++)
	{
		for (int x = 0; x < colSize; x++)
		{
			minContinuousOne = MIN(howManyContinuousOneOnRight[x + y * colSize], howManyContinuousOneOnDown[x + y * colSize]);
			if (minContinuousOne == 0) continue;

			if (minContinuousOne == 1)
			{
				maxEdgeLen = MAX(maxEdgeLen, 1);
				continue;
			}

			x1 = x + minContinuousOne - 1;
			y1 = y + minContinuousOne - 1;
			if (howManyContinuousOneOnDown[x1 + y * colSize] >= minContinuousOne && howManyContinuousOneOnRight[x + y1 * colSize] >= minContinuousOne)
			{
				maxEdgeLen = MAX(maxEdgeLen, minContinuousOne);
			}
		}
	}

	free(howManyContinuousOneOnRight);
	free(howManyContinuousOneOnDown);
	return maxEdgeLen;
}

/**
 * 给定一个N*N的矩阵matrix, 只有0和1两种值，返回边框全是1的最大正方形的边长长度。
 * 例如:
 * 01111
 * 01001
 * 01001
 * 01111
 * 01011
 * 其中边框全是1的最大正方形的大小为4*4，故返回4.
 */
int main_SquareSideLength()
{
	int colSize = 5;
	int matrix[] =
	{
		1,1,1,0,1,
		0,0,1,0,1,
		0,1,0,1,1,
		1,1,1,0,1,
		1,0,0,1,1,
	};

	int rowSize = sizeof(matrix) / (sizeof(int) * colSize);
	int maxEdgeLength = preprocessing(matrix, rowSize, colSize);
	printf("%d", maxEdgeLength);

	return 0;
}